#!/usr/bin/python
# -*- coding:utf-8 -*-
#鸽巢排序
#@author: wklken@yeah.net

#仅对正

def pigeonhole_sort(l):
    #1确定鸽巢个数
    pigeon_size = l[0]
    for i in l:
        if i > pigeon_size:
            pigeon_size = i
    #2初始化鸽巢
    pigeon_hole = [0] * (pigeon_size+1)
    result = []
    print pigeon_hole
    for i in l:
        pigeon_hole[i] += 1
    print pigeon_hole
    for j in range(pigeon_size+1):
        for k in range(pigeon_hole[j]):
            result.append(j)
    return result
l = [8,  3, 7, 6, 5,  1,1 , 9 ,7,17]
print pigeonhole_sort(l)     